The No-U-Turn-Sampler

Computational Statistics Project

Jonathan Fitter (jfitter@wu.ac.at)
Max Heinze (mheinze@wu.ac.at)

Department of Economics, Vienna University of Economics and Business (WU Vienna)

May 27, 2025

 

 

 

Intro and Recap

Hamiltonian Monte Carlo

The No-U-Turn-Sampler (NUTS)

Empirical Stuff

Markov Chain

A Markov chain is a stochastic process \(\{X_t\}\) indexed by time \(t\geq 0\).

  • We call the set of all values that \(\{X_t\}\) can assume the state space of the Markov Chain.
  • \(\{X-t\}\) is called a Markov Chain if it fulfills the Markov property that \[ P(X_{t+1}=j\mid X_0=i_0,\dots,X_t=i_t)=P(X_{t+1}=j\mid X_t=i_t), \] i.e., that the conditional distribution of the next state depends only on the current state.

Markov Chain Monte Carlo (MCMC) methods make use of Markov chains to sample from a target distribution.

Markov Chain

A B C 0.5 0.3 0.2 0.6 0.4 0.7 0.3

Markov chains are

  • irreducible, i.e. every state can eventually be reached from any state;
  • aperiodic, i.e. reverting to a state is not only possible after a multiple of a certain number of steps;
  • positive recurrent, i.e. for all states, the expected number of transitions to return to that state is finite.

For such Markov Chains, transition probabilities converge to a unique stationary distribution on the state space.

Metropolis-Hastings

i j k g ( j | i ) α ( i,j ) 1 − h = i g ( h | i ) α ( i,h ) g ( i | j ) α ( j,i ) g ( k | j ) α ( j,k ) g ( i | k ) α ( k,i ) 1 − h = k g ( h | k ) α ( k,h )

Metropolis-Hastings is a class of MCMC methods.

  • Propose \(Y\sim g(\cdot\mid X_t)\), compute \(\alpha(i,j)=\min\Bigl(1,\frac{f(j)\,g(i\mid j)}{f(i)\,g(j\mid i)}\Bigr)\).
  • If \(U\le\alpha(i,j)\), move \(i\to j\); else stay at \(i\).
  • Chain is reversible and has \(f\) as its stationary distribution.

 

 

Intro and Recap

Hamiltonian Monte Carlo

The No-U-Turn-Sampler (NUTS)

Empirical Stuff

 

Origins in Physics

Imagine a frictionless puck on a non-even surface. The state of this system is given by

  • \(\boldsymbol{q}\), the position of the puck;
  • \(\boldsymbol{p}\), the momentum of the puck, given by \(\mathrm{mass}\times\mathrm{velocity}\).
  • If the puck encounters a rising slope, momentum will decrease; if it encounters a falling slope, momentum will increase.
  • The higher the surface at a position, the higher the puck’s potential energy, and the lower its kinetic energy.

From Physics to Statistics

In non-physical applications,

  • the position \(\boldsymbol{q}\) corresponds to the variables of interest
  • the momentum \(\boldsymbol{p}\) corresponds to the negative log of the probability density for these variables.

Hamiltonian Dynamics

Neal (2012)

Text

Slide Title

  • This
  • is
  • some
  • text.

 

Intro and Recap

Hamiltonian Monte Carlo

The No-U-Turn-Sampler (NUTS)

Empirical Stuff

 

 

Slide Title

  • This
  • is
  • some
  • text.

Intro and Recap

Hamiltonian Monte Carlo

The No-U-Turn-Sampler (NUTS)

Empirical Stuff

 

 

 

Slide Title

  • This
  • is
  • some
  • text.

References

This list is scrollable.

Hoffman, M. D., Gelman, A., et al. (2014). The no-u-turn sampler: Adaptively setting path lengths in hamiltonian monte carlo. J. Mach. Learn. Res., 15(1), 1593–1623.
Neal, R. M. (2012). MCMC using hamiltonian dynamics. https://doi.org/10.48550/ARXIV.1206.1901